// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.core;

import java.util.Iterator;

import com.thalesgroup.graphFramework.collections.DisjointSet;
import com.thalesgroup.graphFramework.collections.MapArrayList;
import com.thalesgroup.graphFramework.collections.MapList;

public class VerticesPartition<V, E> {

	protected DisjointSet dSet;

	protected Graph<V, E> graph;

	public VerticesPartition(final Graph<V, E> graph) {
		final int size = graph.getVerticesSize();
		dSet = new DisjointSet(size);
		this.graph = graph;
	}

	public Graph<V, E> getGraph() {
		return graph;
	}

	public void union(final Vertex<V, E> v1, final Vertex<V, E> v2) {
		dSet.union(v1.getIndex(), v2.getIndex());
	}

	public Vertex<V, E> findLeader(final Vertex<V, E> v) {
		return graph.getVertex(dSet.findSet(v.getIndex()));
	}

	public MapList<Vertex<V, E>, Vertex<V, E>> getPartitions() {
		final MapList<Vertex<V, E>, Vertex<V, E>> leaders = new MapArrayList<Vertex<V, E>, Vertex<V, E>>();

		for(Iterator<Vertex<V,E>> iv=graph.getVertices(); iv.hasNext();) {
			Vertex<V,E> v=iv.next();
			leaders.add(findLeader(v), v);
		}

		return leaders;
	}
}
